//题目:
// 给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
// 返回 你可以获得的最大乘积 。

// 示例 1:
// 输入: n = 2
// 输出: 1
// 解释: 2 = 1 + 1, 1 × 1 = 1。

// 示例 2:
// 输入: n = 10
// 输出: 36
// 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
 
// 提示:
// 2 <= n <= 58
#include<iostream>
#include<vector>
#include<limits.h>

using namespace std;
//代码
class Solution 
{
public:
    int integerBreak(int n) 
    {
        //1.创建dp表————dp[i]表示：整数i被拆分后的最大乘积
        vector<int> dp(n+1);
        //2.初始化
        dp[1]=dp[2]=1;
        //3.填表————动态转移方程：dp[i]=max(dp[1]*dp[i-1],dp[2]*dp[i-2]...);
        for(int i=3;i<=n;i++)
        {
            for(int j=1;j<i;j++)
                dp[i]=max(dp[i],max(dp[j],j)*max(dp[i-j],i-j));
        }
        //4.确定返回值
        return dp[n];
    }
};